﻿#include "Heap.h"

//初始化
Tree* chushihua(int x)
{
	Tree* ret = (Tree*)malloc(sizeof(Tree));
	ret->arr = NULL;
	ret->len = ret->sz = 0;
	return ret;
}

//销毁
void xiaohui(Tree* t)
{
	assert(t);
	free(t->arr);
	free(t);
}


//交换
void swap(dataType* e1, dataType* e2)
{
	dataType  tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//向上调整
void xiangshangtiaozheng(dataType* arr, int i) {
	while (i > 0 && arr[i] < arr[(i - 1) / 2]) {
		swap(&(arr[i]), &(arr[(i - 1) / 2]));
		i = (i - 1) / 2;
	}
}

//插入元素
void push(Tree* t, dataType x) {
	assert(t);
	if (t->sz == t->len) {
		int newlen = t->arr == NULL ? 4 : t->len * 2;
		t->arr = (dataType*)realloc(t->arr, sizeof(dataType) * newlen);
		t->len = newlen;
	}
	(t->arr)[t->sz++] = x;
	xiangshangtiaozheng(t->arr, t->sz - 1);
}

//向下调整
void xiangxiatiaozheng(dataType* arr, int i, int sz) {
	while (i * 2 + 1 < sz) {
		int chile = i * 2 + 1;
		if (chile + 1 < sz && arr[chile + 1] < arr[chile]) {
			chile++;
		}
		if (arr[i] > arr[chile]) {
			swap(&arr[i], &arr[chile]);
			i = chile;
		}
		else return;
	}
}

//删除根元素
void pop(Tree* t)
{
	assert(t && t->sz > 0);
	swap(&t->arr[0], &t->arr[t->sz - 1]);
	t->sz--;
	xiangxiatiaozheng(t->arr, 0, t->sz);
}

//获得根节点元素
dataType top(Tree* t)
{
	assert(t && t->sz);
	return t->arr[0];
}

//判断是否为空堆
bool isEmpty(Tree* t)
{
	assert(t);
	return 0 == t->sz;
}

//堆排序(降序，建小堆)
void sort(int* arr, int sz)
{
	//向上调整建堆 时间复杂度 N*longN
	/*for (int i = 1; i < sz; i++) {
		xiangshangtiaozheng(arr, i);
	}*/
	//向下调整建堆 时间复杂度 N
	for (int i = (sz - 2) / 2; i >= 0; i--) {
		xiangxiatiaozheng(arr, i, sz);
	}
	int end = sz - 1;
	while (end > 0) {
		swap(&arr[0], &arr[end]);
		xiangxiatiaozheng(arr, 0, end);
		end--;
	}
}